The present invention relates in general to computer animation techniques. More particularly, the invention provides a method and system for visibility determination and processing. Merely by way of example, the invention is described as it applies to a rendering process, but it should be recognized that the invention has a broader range of applicability.
Throughout the years, movie makers have often tried to tell stories involving make-believe creatures, far away places, and fantastic things. To do so, they have often relied on animation techniques to bring the make-believe to “life.” Two of the major paths in animation have traditionally included, drawing-based animation techniques and stop motion animation techniques.
Drawing-based animation techniques were refined in the twentieth century, by movie makers such as Walt Disney and used in movies such as “Snow White and the Seven Dwarfs” and “Fantasia” (1940). This animation technique typically required artists to hand-draw or paint animated images onto a transparent media or cels. After painting, each cel would then be captured or recorded onto film as one or more frames in a movie.
Stop motion-based animation techniques typically required the construction of miniature sets, props, and characters. The filmmakers would construct the sets, add props, and position the miniature characters in a pose. After the animator was happy with how everything was arranged, one or more frames of film would be taken of that specific arrangement. Stop motion animation techniques were developed by movie makers such as Willis O'Brien for movies such as “King Kong” (1933). Subsequently, these techniques were refined by animators such as Ray Harryhausen for movies including “Mighty Joe Young” (1948) and “Clash Of The Titans” (1981).
With the wide-spread availability of computers in the later part of the twentieth century, animators began to rely upon computers to assist in the animation process. This included using computers to facilitate drawing-based animation, for example, by painting images, by generating in-between images (“tweening”), and the like. This also included using computers to augment stop motion animation techniques. For example, physical models could be represented by virtual models in computer memory, and manipulated.
One of the pioneering companies in the computer aided animation (CAA) industry was Pixar. Pixar developed both computing platforms specially designed for CAA, and animation software now known as RenderMan®. RenderMan® was particularly well received in the animation industry and recognized with two Academy Awards®. RenderMan® software is used to convert graphical specifications of objects and convert them into one or more images. This technique is known generally in the industry as rendering.
In a rendering process, for example, certain geometric primitives are bounded by bounding boxes. These bounding boxes are usually sorted from front to back with respect to an image plane. Based on the order of the bonding boxes, the respective geometric primitives are processed with an occlusion buffer. The occlusion buffer facilitates the rendering of the primitives onto the image plane.
For example, a list of geometric primitives is sorted from front to back based on locations of their respective bounding boxes. The geometric primitive first in the list is diced into a grid which is then shaded. After the grid is shaded, z values of its micropolygons are stored in an occlusion buffer. The stored information is organized according to locations of the projected images of the micropolygons on the image plane. For example, the occlusion buffer has a resolution equal to the pixel subsample resolution. The z values represent distances of these micropolygons to the image plane. If there is no visible micropolygon corresponding to a given location of the image plane, the occlusion buffer stores a value of infinity for this given location.
After location information of the first primitive is stored in the occlusion buffer, other geometric primitives are processed. For these geometric primitives, occlusion culling may be performed. The occlusion culling would discard a geometric primitive under certain conditions. As discussed above, the geometric primitive is surrounded by a bounding box, and this bounding box has a projected image on the image plane. The location of the projected image may overlap with certain locations on the image plane that have corresponding z values stored in the occlusion buffer. If all these corresponding z values are smaller than the minimum z value of the bounding box, the geometric primitive is not visible. The geometric primitive is then discarded without dicing and shading. If one or more of these corresponding z values are larger than the minimum z value of the bounding box, the one or more z values are updated and the geometric primitive is diced and shaded.
To speed up the visibility determination and processing, a simple hierarchy can be introduced to the occlusion buffer. For example, the hierarchy includes two occlusion buffers. One has the pixel resolution, and the other has the bucket resolution. A bucket usually refers to a portion of a frame. The buffer with pixel resolution stores the minimum z values of all subpixels within a pixel, while the buffer with bucket resolution stores the minimum z values of all pixels within a bucket. These two occlusion buffers can speed up the visibility determination and processing. For example, a geometric primitive has a bounding box with a minimum z value. If the minimum z value is greater than all the corresponding z values in the buffer with bucket resolution, the geometric primitive can be determined to be invisible without comparing with any z values in the occlusion buffer with pixel resolution.
Additionally, the efficiency of the occlusion buffer is improved by the tentative hiding technique. The tentative hiding technique includes busting the grid of a geometric primitive into micropolygons and hit testing the micropolygons immediately prior to shading. If any of the micropolygons are sampled, the grid is considered to be visible. The grid is then shaded and turned into colored micropolygons. If the entire list of micropolygons remains unsampled during hit testing, the grid is fully occluded.
Even with tentative hiding, the occlusion buffer technique still sorts geometric primitives from front to back based on locations of bounding boxes. The bounding boxes are usually loose around the geometric primitives. For example, some geometric primitives occluding each other may have loose bounding boxes that overlap, or may be sorted in the wrong order. Thus geometric primitives that are occluded by other primitives behind them in the sorted list may be rendered first, thus wasting shading efforts.
Hence it is highly desirable to improve techniques for visibility determination and processing in rendering processes.